/*
Problem:    Combinations
Notes:
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
    	vector<vector<int> > result;
    	vector<int> items;
    	FindAllSolutions(n, k, 0, 0, &items, &result);
    	return result;
    }

    void FindAllSolutions(int n, int k, int last_index, int cur_num, vector<int>* items, 
    	vector<vector<int> >* result) {
    	if (cur_num == k) {
    		result->push_back(*items);
    		return;
    	}
    	for (int i = last_index + 1; i <= n; i++) {
    		items->push_back(i);
    		FindAllSolutions(n, k, i, cur_num + 1, items, result);
    		items->pop_back();
    	}
    }
};

int main(int argc, char* argv[])
{
	Solution s;
	vector<vector<int> > result = s.combine(4, 2);
	for (int i = 0; i < result.size(); i++) {
		for (int j = 0; j < result[i].size(); j++)
			cout << result[i][j] << " ";
		cout << endl;
	}
	return 0;
}